//
//  main.cpp
//  矩阵连乘
//  Created by 杨帆 on 2017/4/5.
//  Copyright © 2017年 杨帆. All rights reserved.
//

#include <iostream>
#include <iomanip>

using namespace std;

/**
 * 矩阵连乘
 * @param p 输入的矩阵数组
 * @param n p的长度
 * @param m 保存结果的值
 * @param s 记录最优断开位置的s
 */
void ChainMul(int p[8] , int n , int m[8][8] , int s[8][8])
{
    for (int i = 1; i <= n ; ++i)
    {
        m[i][i] = 0;
    }
    for (int r = 2; r <= n; ++r)
    {
        for (int i = 1; i <= n - r + 1; ++i)
        {
            int j = i + r - 1;
            m[i][j] = m[i + 1][j] + p[i-1] * p[i] * p[j];
            s[i][j] = i;
            for (int k = i + 1; k < j; ++k)
            {
                int t = m[i][k] + m[k+1][j] + p[i-1] * p[k]*p[j];
                if (t < m[i][j])
                {
                    m[i][j] = t;
                    s[i][j] = k;
                }
            }
        }
    }
}


int main()
{
    int m[8][8] = {0};
    int s[8][8] = {0};
    int p[8] = { 0 , 30 , 35 , 15 , 5 , 10 , 20 , 25};


    ChainMul(p , 7 , m ,s);

    for (int j = 2; j < 8; ++j)
    {
        for (int i = 2; i < 8; ++i)
        {
            cout << setw(10) << m[j][i];
        }
        cout << endl;
    }

    cout << "------------" << endl;

    for (int j = 2; j < 8; ++j)
    {
        for (int i = 2; i < 8; ++i)
        {
            cout << setw(10) << s[j][i];
        }
        cout << endl;
    }

    return 0;
}